The computing community has developed tools and methods to analyze the run-time behavior of a computer program. Many of the tools and methods use statistical sampling and binary instrumentation techniques. Statistical sampling is performed by recording periodic snapshots of the program's state, e.g., the program's instruction pointer. Sampling imposes low overhead on a program's run time performance, is relatively non-intrusive, and imprecise. For example, a sampled instruction pointer may not be related to the instruction address that caused a particular sampling event.
While binary instrumentation leads to more precise results, the accuracy comes at some cost to the run-time performance of the instrumented program. Because the binary code of a program is modified, all interactions with the processor and the operating system can change significantly. For example, additional instructions and changes to a program's cache and paging behaviors can cause significant run-time performance degradation. Consequently, binary instrumentation is considered intrusive.
Dynamic binary instrumentation allows program instructions to be changed on-the-fly and leads to a whole class of more precise run-time monitoring results without significant run-time performance increases. Unlike static binary instrumentation techniques that are applied over an entire program prior to execution of the program, dynamic binary instrumentation is performed at run-time of a program and only instruments those portions of an executable that are executed. Consequently, dynamic binary instrumentation techniques can significantly reduce the overhead imposed by the instrumentation process.
Software development tools can combine statistical sampling and dynamic binary instrumentation methods into a framework that enables performance analysis, profiling, coverage analysis, correctness checking, and testing of a program.
A basic reason for the difficulty in testing the correctness of a program is that program behavior largely depends on the data on which the program operates and, in the case of interactive programs, on the information (data and commands) received from a user. Therefore, even if exhaustive testing is impossible, as is often the case, program verification is preferably conducted by causing the program to operate with some data.
Program verification encompasses execution of the program as a process “threads” to determine if the process develops in the correct way or if undesired or unexpected events occur. A “process” is commonly defined as an address space, one or more control threads operating within the address space, and the set of system resources needed for operating with the threads. Therefore, a “process” is a logic entity consisting of the program itself, the data on which it operates, the memory resources, and input/output resources.
Generally, software development tools use two basic techniques to controllably execute program instructions, tracing functions, or tracers and symbolic analysis functions, or symbolic debuggers.
Tracing functions modify a program to be tested so that select program instructions are preceded and followed by overhead instructions that extract variable information, control execution of the instruction, and can monitor program execution. Symbolic debuggers are interactive programs, which translate a high-level language source program to be tested into a compiled program. Symbolic debuggers modify an executable copy of the source selectively inserting conditional branches to other routines, instruction sequences, and break points. The compiled and instrumented program can then be run under the control of a managing program or a software engineer via a human machine interface.
Symbolic debuggers also enable the insertion of instruction sequences for recording variables used in execution of the instruction and on user request, can add and remove break points, modify variables, and permit modification of the hardware environment. These techniques are particularly effective in that they permit step-by-step control of the execution of a program, that is, they allow the evolution of the related process to be controlled by halting and restarting the process at will and by changing parameters during the course of execution of the process. The tools also can display the execution status of the process to the software engineer in detail by means of display windows or other output devices that enable the user to continuously monitor the program. Some conventional tools automate the process of setting break points in the executable version of the source code.
Symbolic debuggers have several limitations. First, they operate on only a single process at a time. Second, because the process to be tested is generated as a child of the symbolic analysis parent, and in a certain sense is the result of a combination of the symbolic analysis function/program with the program to be tested, the two processes must share or utilize the same resources. As a consequence, interactive programs that use masks and windows on a display device cannot be tested because they compete or interfere with the symbolic debugger in requiring access to the display device.
One operating system that has gained widespread acceptance is the UNIX® operating system. UNIX® is a trademark of the American Telephone and Telegraph Company of New York, N.Y., U.S.A.
The UNIX® operating system is a multi-user, time-sharing operating system with a tree-structured file system. Other noteworthy functional features are its logical I/O capabilities, pipes, and forks. The logical I/O capabilities allow a user to specify the input and output files of a program at runtime rather than at compile time, thus providing greater flexibility. Piping is a feature that enables buffering of input and output data to and from other processes. Forking is a feature that enables the creation of a new process.
By themselves, these features offer no inherent benefits. However, the UNIX® operating system command environment (called the SHELL) provides easy access to these operating system capabilities and also allows them to be used in different combinations. With the proper selection and ordering of system commands, logical I/O, pipes, and forks, a user at the command level can accomplish tasks that on other operating systems would require writing and generating an entirely new program. This ability to easily create application program equivalents from the command level is one of the unique and primary benefits of the UNIX® operating system.
The popularity of the UNIX® operating system has led to the creation of numerous open source and proprietary variations such as LINUX®, HP-UX®, PRIMIX®, etc. LINUX® is a trademark of William R. Della-Croce, Jr. (individual) of Boston, Mass., U.S.A. HP-UX®, is a trademark of the Hewlett-Packard Company, of Palo Alto, Calif., U.S.A. PRIMIX® is a trademark of Primix Solutions, Inc., of Watertown, Massachusetts, U.S.A. These and other variants of the UNIX® operating system inherently use the UNIX® operating system's logical I/O capabilities, pipes, and forks.
Software development tools can encounter a number of undesirable conditions when an instrumented process under test includes a “vfork” instruction. The operation of a “vfork” instruction in the UNIX® operating system involves spawning a new process, and then copying the process image of the parent (the process making the vfork call) to the child process (the newly spawned process). The parent process is suspended until the child process terminates. Consequently, the child process inherits any changes made to the address space of the parent process before the child is created and any change made to the address space of the child process necessarily changes the address space of the parent process.
The dynamic instrumentation process changes the address space of a target application. More specifically, it inserts breakpoints into the function entry points in the text region. When an instrumented target process executes a vfork instruction, the child process inherits the text region containing the breakpoints from the parent (i.e., the target) process.
FIG. 1 illustrates a deadlock condition. Deadlock condition 10 occurs between development tool 20, parent process 30, and child process 40 as follows. Development tool 20 instruments parent process 30 as indicated in function 22. A process identifier (process ID) is assigned to the parent process 30 in function 24. Next, the development tool 20 monitors execution of the parent process using trace control as shown in function 26. Under the UNIX® operating system and its open source and proprietary variants, development tool 20 waits for trace events that include the process ID of the parent process as indicated in function 28. Development tool 20 cannot monitor child process 40, since child process 40 has not been created.
Once parent process 30 is created and started, parent process 30 runs nominally in accordance with its instructions until it encounters a vfork instruction as shown in function 32. Thereafter, as shown in function 34, a process ID, different from the parent process ID, is assigned to the child process, to identify the child process. In accordance with the vfork instruction, parent process 30 copies itself in its instrumented state to spawn child process 40 and generates a trace event which is received by development tool 20. Thereafter, as shown in function 38, parent process 30 is essentially suspended waiting for an indication that child process 40 has completed (e.g., indicia of an exec or exit).
Once child process 40 is created by the vfork instruction in parent process 30, child process 40 runs nominally in accordance with its instructions until it encounters the vfork instruction shown in function 42. Thereafter, as shown in function 44, a new process ID, different from the child's process ID is assigned to the subsequent child process, to identify the subsequent child process. As illustrated in function 46, in accordance with the vfork instruction, child process 40 copies itself in its instrumented state to spawn the subsequent child process (not shown) and generates a trace event which is ignored by development tool 20 because development tool 20 is only looking for trace events from parent process 30.
Once the vfork instruction is encountered and processed in child process 40, the deadlock condition has occurred. Parent process 30 is suspended waiting for an indication that child process 40 has completed. Child process 40, which inherited trace control from parent process 30, waits for a process to handle the trace event generated at the time it executed the vfork instruction. Development tool 20 waits for a trace event from parent process 30.
Consequently it is desirable to have an improved apparatus, program, and method for handling vfork instruction induced deadlocks when using debugging techniques to instrument and monitor computer programs. It is also desirable to have an improved apparatus, program, and method for processing breakpoint events encountered during the execution of a child process. It is further desired to process breakpoint events encountered when executing a child process without further modifying the instrumented parent process.